import java.util.DoubleSummaryStatistics;

/*
题目描述：数组中出现超过一半的数字
方法：
1. 直接排序，然后验证中位数     O(nlogn)
2. 使用partition函数          O(n)
3. 利用数组的特点，结果数字出现的次数应该超过其他所有数字出现次数加起来的和
注意的点：
1. 数组为空
2. 数组中位数出现的次数并不一定会超过一半

下面实现方法2(该方法需要修改原数组！！)
 */
public class E39_1 {
    public static void main(String[] args) {
        int[] array = {1,2,3,2,2,2,5,4,2};
        int res = MoreThanHalfNum_Solution(array);
        System.out.println(res);
    }

    public static int MoreThanHalfNum_Solution(int [] array) {
        if(!isValid(array)){
            return 0;
        }
        int mid = array.length >> 1;
        int start = 0;
        int end = array.length - 1;
        int index = partition(array, start, end);
        while(index != mid){
            if(index > mid){
                end = index - 1;
                index = partition(array, start, end);
            }
            else{
                start = index + 1;
                index = partition(array, start, end);
            }
        }
        int res = array[mid];
        if(!CheckMoreThanHalf(array, res)){
            return 0;
        }
        return res;
    }

    public static int partition(int[] array, int begin, int end){
        int pivot = array[begin];
        while(begin < end){
            while(begin < end && array[end] >= pivot){
                end--;
            }
            array[begin] = array[end];
            while(begin < end && array[begin] <= pivot){
                begin++;
            }
            array[end] = array[begin];
        }
        array[begin] = pivot;
        return begin;
    }

    public static boolean CheckMoreThanHalf(int[] array, int num){
        int count = 0;
        for(int a : array){
            if(a == num){
                count ++;
            }
        }
        return count >(array.length >> 1);
    }

    public static boolean isValid(int[] array){
        if(array == null || array.length <= 0){
            return false;
        }
        return true;
    }
}
